/**
 * @file   1102.cpp
 * @author Shuang Hu <hsmath@ubuntu>
 * @date   Sun May  9 03:35:26 2021
 * 
 * @brief  PAT 1102:Invert a Binary-Tree: Another way to store a tree
 * 
 * 
 */
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
bool isroot[10];
class TNode{
public:
    int left;//Mark the index,-1 means NULL.
    int right;
};
class BinaryTree{
private:
    vector<TNode> Nodes;
    int nodenum;
    int root;
public:
    BinaryTree(int nodenum);
    void Level_order();
    void In_order();
    void inordertraverse(int index);
};
int change(char c){
    if(c=='-'){
	return -1;
    }else{
	return c-'0';
    }
}
BinaryTree::BinaryTree(int nodenum){
    this->nodenum=nodenum;
    for(int i=0;i<nodenum;i++){
	isroot[i]=true;
    }
    for(int i=0;i<nodenum;i++){
	TNode T;
	char c1,c2;
	cin>>c1>>c2;
	int d1,d2;
	d1=change(c1);
	d2=change(c2);
	T.left=d2;
	T.right=d1;
	if(d1!=-1){
	    isroot[d1]=false;
	}
	if(d2!=-1){
	    isroot[d2]=false;
	}
	Nodes.push_back(T);
    }
    for(int i=0;i<nodenum;i++){
	if(isroot[i]==true){
	    root=i;
	    break;
	}
    }    
}
void BinaryTree::Level_order(){
    int d=root;
    queue<int> Q;
    Q.push(d);
    bool isfirst=true;
    while(Q.empty()==false){
	int r=Q.front();
	Q.pop();
	if(isfirst==true){
	    cout<<r;
	    isfirst=false;
	}else{
	    cout<<" "<<r;
	}
	if(Nodes[r].left!=-1){
	    Q.push(Nodes[r].left);
	}
	if(Nodes[r].right!=-1){
	    Q.push(Nodes[r].right);
	}
    }
    cout<<endl;
}
void BinaryTree::In_order(){
    inordertraverse(root);
    cout<<endl;
}
void BinaryTree::inordertraverse(int index){
    static bool isfirst=true;
    if(index==-1){
	return;
    }
    inordertraverse(Nodes[index].left);
    if(isfirst==true){
	cout<<index;
	isfirst=false;
    }else{
	cout<<" "<<index;
    }
    inordertraverse(Nodes[index].right);
    return;
}
int main(){
    int nodes;
    cin>>nodes;
    BinaryTree BT(nodes);
    BT.Level_order();
    BT.In_order();
}
